package com.jzoffer;

import java.util.*;

public class RebuildBinaryTree {
    public static void main(String[] args) {
        // 前序
        int[] pre = {1,2,4,5,3,6,7};
        // 中序
        int[] in = {4,2,5,1,6,3,7};

        TreeNode tree = reConstructBinaryTree(pre,in);
        List<Integer> list = preOrder(tree);

        System.out.println(Arrays.toString(preOrder(tree).toArray()));
        System.out.println(Arrays.toString(inOrder(tree).toArray()));
        System.out.println(Arrays.toString(floorOrder(tree).toArray()));

    }

    // 重建二叉树
    public static TreeNode reConstructBinaryTree(int [] pre,int [] in){
        if(pre == null || in == null || pre.length < 1 || in.length < 1){
            return null;
        }
        int preLen = pre.length - 1;
        int inLen = in.length - 1;
        TreeNode treeNode = subReConstructBinaryTree(pre,0,preLen,in,0,inLen);
        return treeNode;
    }

    private static TreeNode subReConstructBinaryTree(int[] pre, int preStart, int preEnd, int[] in, int inStart, int inEnd) {
        // 递归结束条件
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[preStart]);
        // 对中序进行遍历，找到此结点在中序的位置
        for(int i = inStart;i <= inEnd;i++){
            // 固定了i的位置
            if(pre[preStart] == in[i]){
                treeNode.left = subReConstructBinaryTree(pre,preStart + 1,preStart+ i-inStart,in,inStart,i - 1);
                treeNode.right = subReConstructBinaryTree(pre,preStart+i-inStart+1,preEnd,in,i+1,inEnd);
            }
        }
        return treeNode;
    }

    // 前序遍历（非递归）
    public static List<Integer> preOrder(TreeNode treeNode){
        List<Integer> list = new ArrayList<>();
        // 树为空
        if(treeNode == null){
            return list;
        }
        // 使用栈存储
        Stack<TreeNode> stack = new Stack<>();
        stack.push(treeNode);

        while (!stack.isEmpty()){
            TreeNode t = stack.pop();
            list.add(t.val);
            // 先存右子树 再存左子树
            if(t.right != null) {
                stack.push(t.right);
            }
            if(t.left != null){
                stack.push(t.left);
            }
        }

        return list;
    }

    // 中序遍历（非递归）
    private static List<Integer> inOrder(TreeNode treeNode){
        List<Integer> list = new ArrayList<>();
        // 树为空
        if(treeNode == null){
            return list;
        }
        // 使用栈存储
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || treeNode != null){
            if(treeNode != null){
                // 左子树不为空
                stack.push(treeNode);
                treeNode = treeNode.left;
            }else{
                // 左子树为空 结点指向栈顶
                treeNode = stack.pop();
                list.add(treeNode.val);
                treeNode = treeNode.right;
            }
        }
        return list;

    }

    // 后序遍历（递归）
//    private static List<Integer> postOrder(TreeNode treeNode){
//        List<Integer> list = new ArrayList<>();
//        // 树为空
//        if(treeNode == null){
//            return null;
//        }
//        preOrder(treeNode.left);
//        preOrder(treeNode.right);
//        list.add(treeNode.val);
//    }

    // 层序遍历
    private static List<Integer> floorOrder(TreeNode treeNode){
        List<Integer> list = new ArrayList<>();
        // 树为空
        if(treeNode == null){
            return list;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(treeNode);
        while (!queue.isEmpty()){
            TreeNode t = queue.poll();
            list.add(t.val);
            if(t.left != null){
                queue.add(t.left);
            }
            if(t.right != null){
                queue.add(t.right);
            }
        }
        return list;

    }

}

// 二叉树
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
